import java.util.ArrayList;
import java.util.List;

/**
 * @Author cheng.song
 * @create 2022/1/26 17:45
 */
public class 分割回文串 {
    // 用来记录2个下表之间字符串是否为回文串
    // 0未记录 1是 -1不是
    int[][] f;
    int n;
    List<List<String>> ret = new ArrayList<List<String>>();
    List<String> ans = new ArrayList<String>();

    public static void main(String[] args) {
        分割回文串 a = new 分割回文串();
        System.out.println(a.partition("aab"));
    }

    public  List<List<String>> partition(String s) {
        n = s.length();
        f = new int[n][n];

        dfs(s, 0);
        return ret;
    }

    public void  dfs(String s,int i){
        if (i == n) {
            ret.add(new ArrayList<String>(ans));
            return;
        }
        for(int j=i;j<n;j++) {
            if(isHuiwen(s,i,j)==1) {
                ans.add(s.substring(i,j+1));
                dfs(s,j+1);
                ans.remove(ans.size()-1);
            }
        }

    }


    public int isHuiwen(String s,int start,int end){
        if(f[start][end] !=0){
            return f[start][end];
        }
        if(start>=end){
            f[start][end] =1;
        }else if(s.charAt(start) == s.charAt(end)){
            f[start][end] = isHuiwen(s,start+1,end-1);
        }else{
            f[start][end] =-1;
        }
        return f[start][end];
    }
}
